package com.sali.回溯算法;

import java.util.*;

/**
 * 给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
 * <p>
 * 注意：词典中的同一个单词可能在分段中被重复使用多次。
 */
public class LeetCode_140 {

    public static void main(String[] args) {
        String s = "catsanddog";
        List<String> wordDict = new ArrayList<>();
        wordDict.add("cat");
        wordDict.add("cats");
        wordDict.add("and");
        wordDict.add("sand");
        wordDict.add("dog");
        List<String> strings = wordBreak(s, wordDict);
        for (String string : strings) {
            System.out.println(string + " ");
        }

    }

    private static Map<String, List<String>> map = new HashMap<>();

    private static List<String> wordBreak(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        getRes(s, set);
        return map.get(s);
    }

    private static List<String> getRes(String s, Set<String> set) {
        if (map.get(s) != null) {
            return map.get(s);
        }
        List<String> curRes = new ArrayList<>();
        for (int i = 1; i <= s.length(); i++) {
            String tmp = s.substring(0, i);
            if (!set.contains(tmp)) {
                continue;
            }
            if (i == s.length()) {
                curRes.add(tmp);
            } else {
                List<String> innerRes = getRes(s.substring(i), set);
                for (String inner : innerRes) {
                    curRes.add(tmp + " " + inner);
                }
            }
        }
        map.put(s, curRes);
        return curRes;
    }

}
